<!doctype html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>二叉树的最近公共祖先 - 算法详解</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
        }
        .serif-font {
            font-family: 'Noto Serif SC', serif;
        }
        .gradient-bg {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .text-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            -webkit-background-clip: text;
            -webkit-text-fill-color: transparent;
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        .code-block {
            background: #1e1e1e;
            border-radius: 12px;
            overflow: hidden;
        }
        .code-header {
            background: #2d2d2d;
            padding: 12px 20px;
            display: flex;
            align-items: center;
            justify-content: space-between;
        }
        .code-dots {
            display: flex;
            gap: 8px;
        }
        .dot {
            width: 12px;
            height: 12px;
            border-radius: 50%;
        }
        .dot-red { background: #ff5f56; }
        .dot-yellow { background: #ffbd2e; }
        .dot-green { background: #27c93f; }
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
        }
        code {
            font-family: 'Consolas', 'Monaco', 'Courier New', monospace;
            color: #d4d4d4;
            line-height: 1.6;
        }
        .keyword { color: #c586c0; }
        .function { color: #dcdcaa; }
        .string { color: #ce9178; }
        .comment { color: #6a9955; }
        .operator { color: #d4d4d4; }
        .parameter { color: #9cdcfe; }
        @keyframes fadeInUp {
            from {
                opacity: 0;
                transform: translateY(30px);
            }
            to {
                opacity: 1;
                transform: translateY(0);
            }
        }
        .animate-fadeInUp {
            animation: fadeInUp 0.8s ease-out;
        }
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
        .icon-box {
            width: 48px;
            height: 48px;
            display: flex;
            align-items: center;
            justify-content: center;
            border-radius: 12px;
            background: rgba(102, 126, 234, 0.1);
            color: #667eea;
        }
        .section-divider {
            width: 60px;
            height: 4px;
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            border-radius: 2px;
            margin: 1rem 0;
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="gradient-bg text-white py-20 px-6">
        <div class="max-w-4xl mx-auto text-center animate-fadeInUp">
            <div class="flex justify-center mb-6">
                <div class="bg-white bg-opacity-20 rounded-full p-6">
                    <i class="fas fa-tree text-5xl"></i>
                </div>
            </div>
            <h1 class="text-5xl font-bold mb-4 serif-font">二叉树的最近公共祖先</h1>
            <p class="text-xl opacity-90 max-w-2xl mx-auto">
                探索递归思维的优雅之处，掌握树形结构中的经典算法
            </p>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-6xl mx-auto px-6 py-12">
        <!-- Problem Description -->
        <section class="mb-16 animate-fadeInUp" style="animation-delay: 0.2s;">
            <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                <div class="flex items-center mb-6">
                    <div class="icon-box">
                        <i class="fas fa-book-open text-2xl"></i>
                    </div>
                    <h2 class="text-3xl font-bold ml-4 serif-font">题目描述</h2>
                </div>
                <div class="section-divider"></div>
                <p class="text-lg text-gray-700 leading-relaxed mb-6">
                    给定一个二叉树和树中的两个节点 p 和 q，找到该树中这两个节点的最近公共祖先（LCA）。
                </p>
                <div class="bg-purple-50 border-l-4 border-purple-500 p-6 rounded-r-lg">
                    <p class="text-gray-700">
                        <strong class="text-purple-700">最近公共祖先定义：</strong>
                        对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
                    </p>
                </div>
                <div class="mt-6 p-6 bg-gray-50 rounded-lg">
                    <p class="text-gray-600">
                        <i class="fas fa-lightbulb text-yellow-500 mr-2"></i>
                        <strong>示例：</strong>在树 [3,5,1,6,2,0,8,null,null,7,4] 中，节点 5 和节点 1 的最近公共祖先是节点 3。
                    </p>
                </div>
            </div>
        </section>

        <!-- Visual Representation -->
        <section class="mb-16 animate-fadeInUp" style="animation-delay: 0.4s;">
            <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                <div class="flex items-center mb-6">
                    <div class="icon-box">
                        <i class="fas fa-project-diagram text-2xl"></i>
                    </div>
                    <h2 class="text-3xl font-bold ml-4 serif-font">算法可视化</h2>
                </div>
                <div class="section-divider"></div>
                <div class="mermaid">
                    graph TD
                        A[3 - Root/LCA] --> B[5 - Node p]
                        A --> C[1 - Node q]
                        B --> D[6]
                        B --> E[2]
                        C --> F[0]
                        C --> G[8]
                        E --> H[7]
                        E --> I[4]
                        
                        style A fill:#667eea,stroke:#fff,stroke-width:3px,color:#fff
                        style B fill:#ff6b6b,stroke:#fff,stroke-width:3px,color:#fff
                        style C fill:#4ecdc4,stroke:#fff,stroke-width:3px,color:#fff
                        style D fill:#f8f9fa,stroke:#dee2e6
                        style E fill:#f8f9fa,stroke:#dee2e6
                        style F fill:#f8f9fa,stroke:#dee2e6
                        style G fill:#f8f9fa,stroke:#dee2e6
                        style H fill:#f8f9fa,stroke:#dee2e6
                        style I fill:#f8f9fa,stroke:#dee2e6
                </div>
                <div class="grid grid-cols-3 gap-4 mt-8">
                    <div class="text-center">
                        <div class="inline-block w-4 h-4 rounded-full bg-purple-500 mr-2"></div>
                        <span class="text-gray-700">最近公共祖先 (LCA)</span>
                    </div>
                    <div class="text-center">
                        <div class="inline-block w-4 h-4 rounded-full bg-red-500 mr-2"></div>
                        <span class="text-gray-700">节点 p</span>
                    </div>
                    <div class="text-center">
                        <div class="inline-block w-4 h-4 rounded-full bg-teal-500 mr-2"></div>
                        <span class="text-gray-700">节点 q</span>
                    </div>
                </div>
            </div>
        </section>

        <!-- Core Concepts -->
        <section class="mb-16 animate-fadeInUp" style="animation-delay: 0.6s;">
            <div class="grid md:grid-cols-2 gap-8">
                <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                    <div class="flex items-center mb-4">
                        <div class="icon-box">
                            <i class="fas fa-brain text-2xl"></i>
                        </div>
                        <h3 class="text-2xl font-bold ml-4">核心考点</h3>
                    </div>
                    <div class="section-divider"></div>
                    <ul class="space-y-3">
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-purple-500 mt-1 mr-3"></i>
                            <span class="text-gray-700">递归思维与分治策略</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-purple-500 mt-1 mr-3"></i>
                            <span class="text-gray-700">深度优先搜索 (DFS)</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-purple-500 mt-1 mr-3"></i>
                            <span class="text-gray-700">二叉树的遍历与性质</span>
                        </li>
                    </ul>
                </div>
                
                <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                    <div class="flex items-center mb-4">
                        <div class="icon-box">
                            <i class="fas fa-chart-line text-2xl"></i>
                        </div>
                        <h3 class="text-2xl font-bold ml-4">复杂度分析</h3>
                    </div>
                    <div class="section-divider"></div>
                    <div class="space-y-4">
                        <div class="flex items-center justify-between p-4 bg-purple-50 rounded-lg">
                            <span class="font-semibold text-purple-700">时间复杂度</span>
                            <span class="text-2xl font-bold text-purple-600">O(n)</span>
                        </div>
                        <div class="flex items-center justify-between p-4 bg-teal-50 rounded-lg">
                            <span class="font-semibold text-teal-700">空间复杂度</span>
                            <span class="text-2xl font-bold text-teal-600">O(h)</span>
                        </div>
                        <p class="text-sm text-gray-600 mt-2">
                            <i class="fas fa-info-circle mr-1"></i>
                            其中 n 为节点数，h 为树的高度
                        </p>
                    </div>
                </div>
            </div>
        </section>

        <!-- Solution Approach -->
        <section class="mb-16 animate-fadeInUp" style="animation-delay: 0.8s;">
            <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                <div class="flex items-center mb-6">
                    <div class="icon-box">
                        <i class="fas fa-route text-2xl"></i>
                    </div>
                    <h2 class="text-3xl font-bold ml-4 serif-font">解题思路</h2>
                </div>
                <div class="section-divider"></div>
                
                <div class="space-y-6">
                    <div class="flex items-start">
                        <div class="flex-shrink-0 w-10 h-10 bg-purple-100 rounded-full flex items-center justify-center mr-4">
                            <span class="text-purple-600 font-bold">1</span>
                        </div>
                        <div>
                            <h4 class="font-semibold text-lg mb-2">基础情况判断</h4>
                            <p class="text-gray-700">如果当前节点为空，或者当前节点就是 p 或 q，直接返回当前节点。</p>
                        </div>
                    </div>
                    
                    <div class="flex items-start">
                        <div class="flex-shrink-0 w-10 h-10 bg-purple-100 rounded-full flex items-center justify-center mr-4">
                            <span class="text-purple-600 font-bold">2</span>
                        </div>
                        <div>
                            <h4 class="font-semibold text-lg mb-2">递归搜索</h4>
                            <p class="text-gray-700">分别在左右子树中递归查找 p 和 q。</p>
                        </div>
                    </div>
                    
                    <div class="flex items-start">
                        <div class="flex-shrink-0 w-10 h